1. Field of the Invention
The present invention relates generally to an apparatus and method for channel encoding in a communication/broadcasting system, and more particularly, to an apparatus and method for encoding an input symbol using a Fountain code.
2. Description of the Related Art
Ideally, a communication/broadcasting system is capable of transmitting information without errors on a communication/broadcasting channel. For example, if the communication/broadcasting channel has perfect fidelity, a receiver can receive the very same data that a transmitter has transmitted.
In real implementation, however, information is distorted during transmission on the communication/broadcasting channel due to noise, fading, and Inter-Symbol Interference (ISI), etc. Therefore, different technologies for overcoming information distortion have been developed.
Extensive research has recently been conducted on error-correction codes to increase the reliability of communication/broadcasting through efficient correction of information distortion.
To maximize an amount of transmission data, an error-correction code should be designed to have the best performance according to the reliability of a communication/broadcasting channel and the characteristics of transmission information. For example, an error-correction code that is robust against burst errors is often used for a communication/broadcasting channel whose reliability rapidly decreases for a particular time interval, although it has high fidelity for most of time.
An Internet-based protocol, such as Transmission Control Protocol (TCP), adopts Automatic Repeat reQuest (ARQ) to overcome the effects of packet loss.
In ARQ, if a receiver successfully receives a packet from a transmitter, it transmits an ACKnowledgment (ACK) signal to the transmitter. However, if the receiver fails to receive a packet, it transmits a Negative ACK (NACK) signal to the transmitter. When the transmitter receives a NACK signal or does not receive an ACK signal for a transmitted packet from the receiver, the transmitter retransmits the packet to the receiver.
The ARQ scheme ensures efficient information transmission for point-to-point communication between the transmitter and the receiver, in the presence of a feedback channel having high fidelity. However, if a single transmitter transmits information to a plurality of receivers or a plurality of transmitters transmit information to a plurality of receivers, the efficiency of the ARQ scheme rapidly decreases. Moreover, if the feedback channel has low fidelity or the feedback channel is not available, the ARQ scheme is not viable solution.
To solve some of the problems encountered with the ARQ scheme, a multi-to-multipoint transmission system may use erasure codes such as a Reed-Solomon (RS) code.
An RS code is very effective in achieving a channel capacity of an erasure channel. Despite this advantage, however, the RS code is effective only in applications with a limited number of source symbols in view of high encoding and decoding complexity.
An erasure code is characterized in that only if a sufficient number of packets are received, irrespective of packet reception or non-reception, data can be perfectly recovered by decoding the received packets. Most erasure codes have coding rates defined as a ratio between a number of source symbols and a number of encoding symbols. The coding rates are preset when designing the erasure codes.
In a communication/broadcasting system using an erasure code, a transmitter divides data into a plurality of input symbols and generates encoding symbols from the input symbols. Then, the transmitter constructs a packet with the encoding symbols and transmits the packet to a receiver.
Accordingly, the receiver does not transmit an ACK or NACK signal on a packet basis to the transmitter. A packet is an information unit including one or more symbols. However, erasure codes still may not effectively solve the problems of the ARQ scheme or may cause a new problem.
For example, with an erasure code, if the probability of receiving a packet without errors at the receiver is lower than a coding rate, information is not always recovered perfectly. That is, it is difficult for the receiver to perfectly recover information, when the number of received symbols is smaller than the number of source symbols. However, if the probability of receiving a packet without errors at the receiver is higher than the coding rate, information is often recovered perfectly. That is, it is possible for the receiver to perfectly recover information, when the number of received symbols is larger than the number of source symbols. Consequently, system overhead, i.e., the difference between the number of received symbols and the number of source symbols, increases in order to perfectly recover information.
Accordingly, a need exists for an encoding and decoding technique for enabling effective information recovery, without increasing overhead in a communication/broadcasting system.